package com.isaiah.algorithms.search;

/**
 * @Title:  二分查找算法
 * @Description:  https://blog.csdn.net/lzf_hlh/article/details/88601561
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/6/415:04
 */
public class BinarySearch {

    /**
     *  二分查找递归实现
     * @param arr 待查找的数组，arr是有升序排列的
     * @param key 需要查找的元素
     * @return 返回对应的下标
     */
    public static int binarySearch(int[] arr, int key){
        //在这里提前判断一下数组是否为空,如果为空，那就没必要在查找了
        if(arr == null) {
            throw new IllegalArgumentException("array is empty");
        }

        return binarySearch(arr, 0, arr.length, key);
    }
    private static int binarySearch(int[] arr, int low, int hight , int key){
        if (hight > low){
            int mid = (low + hight) / 2;
            if (arr[mid] > key){
                // 在左边查找
                return binarySearch(arr, low, mid - 1, key);
            }else if (arr[mid] < key){
                // 在右边查找
                return binarySearch(arr, mid + 1, hight, key);
            }else{
                // 刚才查找到
                return mid;
            }
        }
        return -1;


    }

    /**
     *  二分查找迭代实现
     * @param arr 待查找的数组，arr是有升序排列的
     * @param key 需要查找的元素
     * @return 返回对应的下标
     */
    public static int binarySearchNR(int[] arr, int key){
        //在这里提前判断一下数组是否为空,如果为空，那就没必要在查找了
        if(arr == null) {
            throw new IllegalArgumentException("array is empty");
        }

        int left = 0;
        int right = arr.length - 1;
        while (left <= right){      // 说明继续查找
            int mid = (left + right) / 2;
            if (arr[mid] == key){
                return mid;
            }else if (arr[mid] > key){
                // 需要在左边查找
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        // 给定一个有序数组
        int[] arr1 = {1, 2, 3, 5, 8};
        System.out.println(binarySearch(arr1, 3));
        System.out.println(binarySearchNR(arr1, 3));


    }

}
